package test.algorithm;

/**
 * 问题描述：给定n种物品和一背包。物品i的重量是w[i]，其价值为v[i]，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
 *
 * 分析：对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1。设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-1背包问题。
 *
 * 数据：物品个数n=5,物品重量w[5]={2，2，6，5，4},物品价值v[5]={6，3，5，4，6},总重量c=10。背包的最大容量为10，那么在设置数组m大小时，可以设行列值为5和10，那么，对于m(i,j)
 * 就表示可选物品为i到n且背包容量为j(总重量)时背包中所放物品的最大价值。看下面这个表格即为动态规划法解0-1背包问题的过程：
 *
 * @author yachao.guo
 * @date 2020/10/16 11:13
 */
public class Backpack {
//
//    public static void main(String[] args) {
//
//        int[] weights = {2, 2, 6, 5, 4};
//        int[] values = {6, 3, 5, 4, 6};
//        int countWeight = 10;
//
//       int[][] m = build(weights,values,countWeight);
//       for(int i=0;i<m.length;i++){
//           for(int j=0;j<m[i].length;j++){
//               System.out.print(m[i][j]+",");
//           }
//           System.out.println(" ");
//        }
//       //int [] x = buildSolution(m,weights,countWeight);
//       // for(int i=0;i<4;i++){
//       //     System.out.print(x[i]+"  ");
//       // }
//    }
//
//    public  static  int[][] build(int[] weights , int[] values ,  int countWeight){
//        int[][] m = new int[weights.length][countWeight+2];
//
//        for(int i=0;i<weights.length;i++){
//            m[i][0]=weights[i];
//            m[i][1]=values[i];
//        }
//        for(int i=0;i<weights.length;i++){
//          for(int j=2;j<countWeight+2;j++){
//              m[i][j] =
//          }
//        }
//return m;
//
//    }
//    //依据m[][]实现对符合结果要求的物品进行选择的构建一个数组存储选择的情况0否1选择
//    public static int[] buildSolution(int[][] m,int[] w,int c){
//        int i,j = c,n = w.length;
//        int[] x = new int[n];
//        for(i=n;i>=1;i--){
//            if(m[i][j]==m[i-1][j]){
//                x[i-1] = 0;
//            }else{
//                x[i-1]=1;
//                j -= w[i-1];
//            }
//        }
//        return x;
//    }

}
